package leetcode.easy.diameterofbinarytree;

import util.adt.TreeNode;
import util.annotation.Solved;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/diameter-of-binary-tree/?envType=study-plan-v2&envId=top-100-liked">543. 二叉树的直径</a>
 *
 * @since 2024/5/31
 */
@Solved
public class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        int diameterLeft = diameterOfBinaryTree(root.left);
        int diameterRight = diameterOfBinaryTree(root.right);
        int leftH = H(root.left);
        int rightH = H(root.right);
        int rootDiameter = 0;
        if (root.left != null) {
            rootDiameter += 1 + leftH;
        }
        if (root.right != null) {
            rootDiameter += 1 + rightH;
        }
        int[] diameters = {diameterLeft, diameterRight, rootDiameter};
        Arrays.sort(diameters);
        return diameters[2];
    }

    private int H(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        return Math.max(1 + H(root.left), 1 + H(root.right));
    }
}
